/**
 * @a https://leetcode.cn/problems/spiral-matrix/description/
 */

#include "../common.h"

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> ret;
        ret.reserve(m * n);

        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;

        while (top <= bottom && left <= right) {
            // 从左到右
            for (int j = left; j <= right; ++j) {
                ret.push_back(matrix[top][j]);
            }
            ++top;

            // 从上到下
            for (int i = top; i <= bottom; ++i) {
                ret.push_back(matrix[i][right]);
            }
            --right;

            // 从右到左
            if (top <= bottom) {
                for (int j = right; j >= left; --j) {
                    ret.push_back(matrix[bottom][j]);
                }
                --bottom;
            }

            // 从下到上
            if (left <= right) {
                for (int i = bottom; i >= top; --i) {
                    ret.push_back(matrix[i][left]);
                }
                ++left;
            }
        }

        return ret;
    }
};
